<template>
  <div class="content">
    <h1>排序</h1>
    <div>原始数组： {{ primaryArr }}</div>
    <h2>原始函数sort</h2>
    <div>输出结果：{{ primarySort() }}</div>
    <div>耗时：{{ speedTime.sort }}ms</div>
    <h2>冒泡排序</h2>
    <div>输出结果：{{ bubbleSort() }}</div>
    <div>耗时：{{ speedTime.bubbleSort }}ms</div>
    <h2>插入排序</h2>
    <div>输出结果：{{ insertSort() }}</div>
    <div>耗时：{{ speedTime.insertSort }}ms</div>
    <h2>递归排序</h2>
    <div>输出结果：{{ mergeSort() }}</div>
    <div>耗时：{{ speedTime.mergeSort }}ms</div>
    <h2>快速排序</h2>
    <div>输出结果：{{ quickSort() }}</div>
    <div>耗时：{{ speedTime.quickSort }}ms</div>
    <h2>选择排序</h2>
    <div>输出结果：{{ selectionSort() }}</div>
    <div>耗时：{{ speedTime.selectionSort }}ms</div>
    <h1> </h1>
    <h1>去重</h1>
    <div>原始数组： {{ primaryArr }}</div>
    <div>长度 {{primaryArr.length}}</div>
    <h2>new Set</h2>
    <div>输出结果：{{ setReset() }}</div>
    <div>长度 {{setReset().length}}</div>
    <div>耗时：{{ resetTime.setReset }}ms</div>
    <h2>对象key不重复去重</h2>
    <div>输出结果：{{ objReset() }}</div>
    <div>长度 {{setReset().length}}</div>
    <div>耗时：{{ resetTime.objReset }}ms</div>
    <h2>indexof去重</h2>
    <div>输出结果：{{ indexofReset() }}</div>
    <div>长度 {{indexofReset().length}}</div>
    <div>耗时：{{ resetTime.indexofReset }}ms</div>
    <h2>splice去重</h2>
    <div>输出结果：{{ spliceReset() }}</div>
    <div>长度 {{spliceReset().length}}</div>
    <div>耗时：{{ resetTime.spliceReset }}ms</div>
    <h2>双层for去重</h2>
    <div>输出结果：{{ forReset() }}</div>
    <div>长度 {{forReset().length}}</div>
    <div>耗时：{{ resetTime.forReset }}ms</div>
  </div>
</template>

<script>
import { indexOf } from "lodash";

export default {
  data() {
    return {
      speedTime: {},
      resetTime: {}
    };
  },
  methods: {
    setReset(){
      let arr = [...this.primaryArr];
      let time = Date.now();
      arr = [...new Set([...arr])];
      this.resetTime.setReset = Date.now() - time;
      return arr;
    },
    indexofReset(){
      let arr = [...this.primaryArr];
      let time = Date.now();
      let newArr = []
      for(let i=0;i<arr.length;i++){
        if(arr.indexOf(arr[i])===i){
          newArr.push(arr[i])
        }
      }
      this.resetTime.indexofReset = Date.now() - time;
      return newArr;
    },
    spliceReset(){
      let arr = [...this.primaryArr];
      let time = Date.now();
      for(let i=0;i<arr.length;i++){
        if(arr.indexOf(arr[i])!==i){
          arr.splice(i,1);
          i--;
        }
      }
      this.resetTime.spliceReset = Date.now() - time;
      return arr;
    },
    forReset(){
      let arr = [...this.primaryArr];
      let time = Date.now();
      let newArr = []
      for(let i=0;i<arr.length;i++){
        for(let j = i+1;j<arr.length;j++){
          if(arr[j]===arr[i]){
            j=++i
          }
        }
        newArr.push(arr[i])
      }
      this.resetTime.forReset = Date.now() - time;
      return newArr;
    },
    objReset(){
      let arr = [...this.primaryArr];
      let time = Date.now();
      let obj = {};
      for(let i=0;i<arr.length;i++){
        obj[arr[i]]=true
      }
      arr = Object.keys(obj)
      this.resetTime.objReset = Date.now() - time;
      return arr;
    },
    // 原始sort
    primarySort() {
      let arr = [...this.primaryArr];
      let time = Date.now();
      arr = arr.sort((a, b) => a - b);
      this.speedTime.sort = Date.now() - time;
      return arr;
    },
    // 冒泡排序 前后两个对比
    bubbleSort() {
      let arr = [...this.primaryArr];
      let time = Date.now();
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
          let temp = 0;
          if (arr[j] > arr[j + 1]) {
            temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
          }
        }
      }
      this.speedTime.bubbleSort = Date.now() - time;
      return arr;
    },
    // 插入排序 当前项往前插入
    insertSort() {
      let arr = [...this.primaryArr];
      let time = Date.now();
      let temp = 0;
      for (let i = 1; i < arr.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
          if (arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          } else break;
        }
      }
      this.speedTime.insertSort = Date.now() - time;
      return arr;
    },
    // 递归排序
    mergeSort(arr = [...this.primaryArr]) {
      // 采用自上而下的递归方法
      const len = arr.length;
      this.speedTime.mergeSort ? "" : (this.speedTime.mergeSort = 0);
      let time = Date.now();
      if (len < 2) {
        return arr;
      }
      let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
      this.speedTime.mergeSort += Date.now() - time;
      return this.merge(this.mergeSort(left), this.mergeSort(right));
    },
    merge(left, right) {
      let time = Date.now();
      const result = [];
      while (left.length && right.length) {
        if (left[0] <= right[0]) {
          result.push(left.shift());
        } else {
          result.push(right.shift());
        }
      }
      while (left.length) result.push(left.shift());
      while (right.length) result.push(right.shift());
      this.speedTime.mergeSort += Date.now() - time;
      return result;
    },
    // 快速排序 推荐
    quickSort() {
      let arr = [...this.primaryArr];
      let time = Date.now();
      arr = this.rec(arr);
      this.speedTime.quickSort = Date.now() - time;
      return arr;
    },
    rec(arr) {
      if (arr.length <= 1) {
        return arr;
      }
      const left = [];
      const right = [];
      const mid = arr[0]; // 基准元素
      for (let i = 1; i < arr.length; i++) {
        if (arr[i] < mid) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
      return [...this.rec(left), mid, ...this.rec(right)];
    },
    // 选择排序
    selectionSort() {
      let arr = [...this.primaryArr];
      let time = Date.now();
      var len = arr.length;
      var minIndex, temp;
      for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
          if (arr[j] < arr[minIndex]) {
            // 寻找最小的数
            minIndex = j; // 将最小数的索引保存
          }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
      this.speedTime.selectionSort = Date.now() - time;
      return arr;
    },
  },
  computed: {
    primaryArr() {
      let arr = [];
      for (let i = 0; i < 10000; i++) {
        const num = Math.floor(100000 * Math.random());
        arr.push(num);
      }
      return arr;
    },
  },
  mounted() {},
};
</script>
<style scoped lang="less">
.content {
  padding: 20px;
  & > div {
    white-space: nowrap;
    width: 100%;
    overflow: hidden;
    text-overflow: ellipsis;
  }
}
</style>
